﻿\subsection{Нижние оценки абелевой границы повторяемости}
\label{subsection:abelian-lower}

Как Дежан в \cite{Dejean}, мы начинаем изучение абелевой границы повторяемости с нижних оценок.
Мы доказываем оценки строгой и слабой абелевой границы повторяемости (обозначаемых $ART_s(k)$ и
$ART_w(k)$ соответственно). На основании экспериментальных данных можно утверждать, что
с большой вероятностью наша оценка для $ART_s(k)$ является точной,
в то время как оценку $ART_w(k)$ можно улучшить.

\begin{thrm} \label{art_strong}
$ART_{s}(k) \ge \frac{k{-}2}{k{-}3}$ для всех $k \ge 5$.
\end{thrm}

Пусть $\Sigma=\{1,\ldots,k\}$, $w = w_{1} \ldots w_{m} \in\Sigma^*$. Подслово $u$ слова $w$ называется
\textit{l-подсловом}, если $|u| = l$. Слово $w_{j} \ldots w_{j{+}l{-}1}$~--- это $j$-е $l$-подслово $w$.
Для всех $j$, $j$-е и $(j{+}1)$-е $l$-подслова $w$ называются \textit{последовательными}. Докажем две леммы.

\begin{lmm} \label{lemma_art_strong1}
Пусть $k \ge 4$, $w \in \Sigma^*$ является строго абелево $\frac{k{-}2}{k{-}3}$-свободным словом.
Тогда:\\
$(1)$ Любое $(k{-}2)$-подслово $w$ состоит из $(k{-}2)$ различных букв;\\
$(2)$ Хотя бы одно из двух последовательных $(k{-}1)$-подслов $w$ состоит из $(k{-}1)$ различной буквы.
\end{lmm}

\begin{proof}
(1) Пусть $w = w_1 \ldots w_m$. Если $w_i = w_j$ для некоторых $i < j$, то $w_i \ldots w_j$
является строгой абелевой $\frac{j{-}i{+}1}{j{-}i}$-степенью.
Поскольку $w$ является абелево $\frac{k{-}2}{k{-}3}$-свободным, то $j-i \ge k-2$.

(2) Пусть $u = w_{i} \ldots w_{i+k{-}2}$ и $v = w_{i+1} \ldots w_{i+k{-}1}$~--- два последовательных
$(k{-}1)$-подслова $w$. $u$ является абелево $\frac{k{-}2}{k{-}3}$-свободным, поэтому из (1) мы получаем, что
первые и последние $(k{-}2)$ буквы $u$ различны, то же верно и для $v$. 
Пусть в $u$ и в $v$ есть две одинаковые буквы. Это значит, что $w_{i} = w_{i+k{-}2}$ и $w_{i+1} = w_{i+k{-}1}$,
откуда $w_{i} \ldots w_{i+k{-}1}$ имеет строгую абелеву экспоненту $\frac{k}{k{-}2}$, что не меньше чем
$\frac{k{-}2}{k{-}3}$ при $k \ge 4$.
\end{proof}

По лемме \ref{lemma_art_strong1}, $\frac{k{-}2}{k{-}3}$-свободные слова над алфавитом размера $k$
имеют $(k{-}1)$-подслова двух типов: \textit{квазиперестановки}, состоящие из различных букв, и
\textit{повторы}, в которых первая и последняя буквы совпадают. \textit{Перестановкой} мы будем называть
$k$-подслово, состоящее из различных букв.

\begin{rmrk} \label{kplus}
Абелевы $\frac{k{+}1}{k{-}1}$-степени ($\frac{k{+}2}{k}$-степени) запрещены в
$\frac{k{-}2}{k{-}3}$-свободном языке над алфавитом размера $k$ при $k\ge 5$ ($k\ge 6$). 
\end{rmrk}

\begin{lmm} \label{lemma_art_strong2}
При $k\ge6$, любое абелево $\frac{k{-}2}{k{-}3}$-свободное слово над алфавитом размера $k$,
начинающееся с квазиперестановки и не содержащее перестановок в качестве подслов, имеет длину не более $4k{-}2$.
\end{lmm}

\begin{proof}
Пусть слово $w$ удовлетворяет условиям леммы. Пусть $j$-е и $(j{+}1)$-е $(k{-}1)$-подслова $w$~--- квазиперестановки.
Тогда они состоят из одних и тех же букв. Тогда $(j{+}2)$-е $(k{-}1)$-подслово $w$~--- повтор,
в противном случае $w$ содержит абелеву $\frac{k{+}1}{k{-}1}$-степень, что невозможно по замечанию~\ref{kplus}. 

Пусть, от противного, $|w|\ge 4k{-}1$. Тогда количество $(k{-}1)$-подслов в $w$ не меньше $3k{+}1$.
Значит, $w$ содержит хотя бы $k$ повторов и квазиперестановку справа от $k$-го (в порядке слева направо) из этих повторов.
Поскольку существует только $k$ различных наборов букв для квазиперестановок, $w$ содержит две квазиперестановки,
которые состоят из одинаковых букв и не являются последовательными.
Пусть $i$-е $(k{-}1)$-подслово $z$ и $j$-е $(k{-}1)$-подслово $\bar{z}$~--- это такие квазиперестановки, что разность
$j{-}i>1$ минимальна. Если $z$ и $\bar{z}$ пересекаются в $w$, они образуют подслово $xy\bar{x}$, такое что $xy=z$
и $y\bar{x}=\bar{z}$. Очевидно, $|x|\ge2$ и $\bar{x}$~--- анаграмма $x$. Значит, $xy\bar{x}$~--- это абелева
$\beta$-степень для некоторого $\beta\ge\frac{k{+}1}{k{-}1}$, что невозможно по замечанию~\ref{kplus}. 

Пусть теперь $z$ и $\bar{z}$ не пересекаются в $w$. Поскольку две последовательных квазиперестановки в $w$
состоят из одинаковых букв, из минимальности $j{-}i$ мы получаем, что $(i{+}1)$-е и $(j{-}1)$-е $(k{-}1)$-подслово
$w$ являются повторами. Рассмотрим слово $u=w_i\ldots w_{j{+}k{-}2}=zy\bar{z}$. Из минимальности $j{-}i$,
$u$ содержит не более чем $k$ повторов, и, соответственно не более чем $3k$ $(k{-}1)$-подслов.
Отсюда мы получаем $|u|\le 4k{-}2$. Слово $u$ является абелевой $\frac{|u|}{|u|{-}k{+}1}$-степенью. При $k\ge7$,
$$
\frac{|u|}{|u|-k+1}\ge\frac{4k-2}{3k-1}\ge\frac{k-2}{k-3},
$$
что противоречит тому, что $w$~--- абелево $\frac{k{-}2}{k{-}3}$-свободное.
Для $k=6$ требуется более подробный анализ. Мы докажем, что в этом случае слово $u$ содержит менее чем $2k=12$
квазиперестановок. Если это число достигается, $u$ содержит пять пар последовательных квазиперестановок помимо $z$
и $\bar{z}$. В этом случае начало $u$ выглядит следующим образом, с точностью до переименования букв
(вспомним, что $u$ не содержит перестановок). Под каждой буквой указан тип $(k{-}1)$-подслова, начинающегося с этой
буквы (q = квазиперестановка, r = повтор):
$$
\arraycolsep=1pt
\begin{array}{cccccccccccccc}
1&2&3&4&5&2&6&3&\pmb5&\pmb1&\pmb2&\pmb3&\pmb4&\ldots\\
q&r&q&q&r&q&q&r&q&&&&&\ldots
\end{array}
$$
Мы видим, что $u$ содержит другую анаграмму $z$ (выделенную жирным), что противоречит выбору $\bar{z}$.
На самом деле, мы доказали, что последовательность $(k{-}1)$-подслов $u$ не содержит подслова $qrqqrqqrq$.
Значит, самая длинная последовательность $(k{-}1)$-подслов $u$ имеет вид $qrqqrqrqqrqrqqrq$, откуда $|u|\le 20$.
Следовательно, $u$ является абелевой $(4/3)$-степенью, в то время как $w$ является абелево $(4/3)$-свободным
по условию леммы. Мы пришли к противоречию.
\end{proof}

\begin{proof}[Доказательство теоремы~\ref{art_strong}]
Пусть Абелева экспонента $\frac{k{-}2}{k{-}3}$ $k$-избегаема, $W$~--- абелево $\frac{k{-}2}{k{-}3}$-свободное бесконечное
слово над алфавитом размера $k$. Рассмотрим случай $k\ge6$. По леммам \ref{lemma_art_strong1} и \ref{lemma_art_strong2},
бесконечное количество $k$-подслов $W$ являются перестановками. Хотя бы одно из любых трёх последовательных
$k$-подслов $W$ не является перестановкой (иначе $W$ содержит абелеву $\frac{k{+}2}{k}$-степень, что невозможно по
замечанию \ref{kplus}). Поэтому мы можем выбрать пару индексов $i,j$, таких что $i{+}1<j$, $i$-е и $j$-е $k$-подслова
$W$ являются перестановками, и $r$-е $k$-подслово $W$ не является перестановкой при $i<r<j$. 

Если две выбранные перестановки пересекаются в $W$, они образуют подслово $xy\bar{x}$, такое что
$|xy|=k$, $|x|\ge2$, и $\bar{x}$~--- анаграмма $x$. Это подслово является абелевой $\beta$-степенью для некоторого
$\beta\ge\frac{k{+}2}{k}$, что невозможно по замечанию \ref{kplus}. С другой стороны, если эти перестановки не
пересекаются в $W$, то в $W$ есть подслово $u=xy\bar{x}$, такое что $x$ и $\bar{x}$ являются перестановками
(и, следовательно, анаграммами друг друга). Если мы удалим первую и последнюю буквы $u$, мы получим
$\frac{k{-}2}{k{-}3}$-свободное слово, которое начинается с квазиперестановки и не содержит перестановок в качестве
подслов. По лемме \ref{lemma_art_strong2}, $|u|{-}2\le 4k{-}2$, т.\,е. $|u|\le 4k$. Следовательно,
$u$ содержит абелеву $\beta$-степень для некоторого $\beta\ge4/3$. Из этого противоречия следует, что $W$ не существует,
поэтому абелева экспонента $\frac{k{-}2}{k{-}3}$ $k$-неизбежна при $k\ge6$.

Случай $k=5$ требуется исследовать отдельно. Это довольно нудный (хотя и не очень длинный) разбор случаев. Мы
опустим его, приведя лишь статистику, подтверждённую компьютерным перебором: антисловарь абелево $(3/2)$-свободного
языка содержит лишь 49 (лексикографически минимальных) слов, а максимальная длина корня запрещённого слова равна 10.
\end{proof}

Теперь обратимся к слабым абелевым степеням.

\begin{thrm} \label{art_weak}
$ART_{w}(k) \ge \frac{k}{k{-}2}$ для всех $k \ge 10$.
\end{thrm}

Пусть $\Sigma=\{1,\ldots,k\}$, $w = w_{1} \ldots w_{m} \in\Sigma^*$. Буква $w_i$ слова $w$ называется
\textit{старой буквой} если $w_i = w_j$ для некоторого $j < i$. Аналогично, $w_i$ является \textit{новой буквой}
если она не встречается в $w_{1} \ldots w_{i{-}1}$. Докажем две леммы.

\begin{lmm} \label{lemma_art_weak1}
Пусть $k \ge 8$, $w \in \Sigma^*$~--- слабо абелево $\frac{k}{k{-}2}$-свободное слово над алфавитом размера $k$,
$w$ заканчивается на $l$ ($1 \le l \le 4$) старых букв. Тогда $2|w| > lk$.
\end{lmm}
\begin{proof}
Все $l$ последних букв $w$ различны, иначе они образуют слабую абелеву степень с экспонентой не меньше
$\frac{4}{3} \ge \frac{k}{k{-}2}$ при $k \ge 8$. Последние $l$ букв старые, поэтому все они встречаются
в $w_{1} \ldots w_{|w|{-}l}$. Следовательно, $w$ является слабой абелевой степенью с экспонентой
$\frac{|w|}{|w|{-}l} < \frac{k}{k{-}2}$, откуда $2|w| > lk$.
\end{proof}

\begin{crllr} \label{coroll_art_weak}
Пусть $k \ge 8$, $w = pqrs$~--- абелево $\frac{k}{k{-}2}$-свободное слово над алфавитом из $k$ букв,
$|p| = |r| = \lfloor\frac{k}{2}\rfloor$, $|q| = |s| = \lceil\frac{k}{2}\rceil$. Тогда\\
$(1)$ $p$ не содержит старых букв;\\
$(2)$ $pq$ не содержит двух последовательных старых букв;\\
$(3)$ $pqr$ не содержит трёх последовательных старых букв;\\
$(4)$ $w = pqrs$ не содержит четырёх последовательных старых букв.
\end{crllr}
\begin{proof}
Если мы рассмотрим префикс слова $pqrs$, заканчивающийся на группу последовательных старых букв,
мы сможем получить ограничение на длину этой группы из леммы~\ref{lemma_art_weak1}.
\end{proof}

\begin{rmrk} \label{remark_art_weak}
Пусть $k \ge 8$, $w$~--- абелево $\frac{k}{k{-}2}$-свободное слово над алфавитом из $k$ букв,
$|w| = \lfloor\frac{k}{2}\rfloor$. Тогда $w$ состоит из $\lfloor\frac{k}{2}\rfloor$ различных букв.\\
\end{rmrk}

\begin{lmm} \label{lemma_art_weak2}
Пусть $k \ge 10$, $w \in \Sigma^*$ является слабо абелево $\frac{k}{k{-}2}$-свободным словом над алфавитом из $k$ букв,
$|w| = 2k$. Тогда $w$ содержит $k$ различных букв.
\end{lmm}
\begin{proof}

Рассмотрим слово $w$ длины $2k$, в котором каждая новая буква встречается
как можно позже в смысле следствия~\ref{coroll_art_weak}. То есть, если мы
запишем $w=pqrs$, где $|p| = |r| = \lfloor\frac{k}{2}\rfloor$ и
$|q| = |s| = \lceil\frac{k}{2}\rceil$, то каждая новая буква в $q$ (в $r$, в $s$)
встречается после одной (соответственно, двух или трёх) старых букв в $w$. Мы назовём такое слово $w$
\textit{поздним}. Очевидно, достаточно доказать, что любое позднее слово содержит $k$
новых букв. Докажем это по индукции. Для базы индукции $k=10$, вхождения
новых букв в $w$ заданы следующей on-\textit{кодировкой} (o\,=\,старая, n\,=\,новая):
\begin{equation}
\mathrm{nnnnn\,onono\,onoon\,ooono},
\end{equation}
и требуемое условие выполняется. Рассмотрим <<чётные>> (переход от $k=2l{-}1$ к $2l$) и
<<нечётные>> (от $k=2l$ к $2l{+}1$) шаги индукции отдельно. При чётном шаге увеличивается длина
$p$ и $r$, а при нечётном шаге увеличивается длина $q$ и $s$.

Чётный шаг доказывается просто. Рассмотрим on-кодировку позднего слова $w=pqrs$ длины
$2k$ и допишем $\mathrm n$ к его началу и $\mathrm o$ к его концу. Если $r$ не заканчивается
на две старых буквы, мы получим on-кодировку позднего слова длины $2k{+}2$.
В противном случае, чтобы получить такую on-кодировку нам потребуется только
сдвинуть все буквы $\mathrm n$ правее этих двух букв на один символ влево (поскольку
первая буква $s$ стала последней буквой $r$). В любом случае, позднее слово длины
$2k{+}2=4l$ содержит $k{+}1$ новую букву. Также заметим, что последняя буква позднего
слова длины $4l$ старая (это утверждение также выполняется для базы индукции).

Теперь докажем нечётный шаг. Пусть $v=p'q'r's'$~--- позднее слово длины $2k{+}2$.
Рассмотрим on-кодировку позднего слова $w=pqrs$ длины $2k=4l$, добавим $\mathrm o$
и $\mathrm n$ в его конец, и сравним полученное слово $z\in\{\mathrm{o,n}\}^*$
c on-кодировкой $v$. Как мы показали выше, последняя буква $w$ старая:

\begin{center}
\includegraphics{pictures/abelian-lower.pdf}
\end{center}

Слово $z$ содержит $k{+}1$ букву $\mathrm n$. Каждая буква $\mathrm n$ в
 $z$, позиция которой соответствует подслову $q'$ (подслову $r'$, подслову $s'$)
слова $v$, следует хотя бы за одной (соответственно, двумя или тремя) буквами
$\mathrm o$. Единственное возможное исключение~--- последняя буква $\mathrm n$ в $z$.
Поэтому, если $w$ заканчивается на две старых буквы, то исключение не встречается,
и позиция $j$-й новой буквы в $v$ не больше позиции $j$-й буквы $\mathrm n$ в $z$.
для всех $j=1,\ldots, k{+}1$. В результате, $v$ заведомо содержит $k{+}1$ новую букву,
и шаг индукции доказан. Случай, когда предпоследняя буква $w$ новая, ведёт к
исключению, и исследуется в последней части доказательства.

Предполагая, что on-кодировка $w$ заканчивается на $\,\mathrm{no}$, мы
рассматриваем три случая, в зависимости от позиции $j$ первой новой буквы в $s$.
Если $j$~--- это вторая позиция в $s$, мы сдвинем все $\mathrm n$, соответствующие
подслову $s$ слова $w$, на один символ влево в слове $z$. Поскольку
в этом случае $(j{-}1)$-я позиция соответствует подслову $r'$ слова $v$,
полученное слово $z'$ обладает требуемым свойством: каждая буква $\mathrm n$,
позиция которой соответствует подслову $q'$ (подслову $r'$, подслову $s'$) слова $v$,
идёт после как минимум одной (соответственно, двух или трёх) букв $\mathrm o$.
Как и выше, мы заключаем, что в $v$ содержится $k{+}1$ новая буква. Если $j$~---
это четвёртая позиция в $s$, тогда $l=|s|$ нечётно, поскольку позиции новых букв в $s$
равны по модулю 4. Тогда $q$ заканчивается на старую букву, откуда вторая буква $r$
новая. Мы сдвигаем все буквы $\mathrm n$, соответствующие подсловам $r$ и $s$ слова $w$,
на один символ влево в слове $z$. Повторяя те же рассуждения, мы получаем, что
в $v$ содержится $k{+}1$ новая буква.

Осталось рассмотреть случай, когда $j$~--- третья позиция в $s$. Тогда $l=|s|$
кратно 4. Следовательно, последняя буква $q$ новая. Поскольку последняя буква
$q$ и третья буква $s$ новые, третья и предпоследняя буквы $r$ тоже новые.
Следовательно, $l=|r|=3l'{+}1$. Заметим, что $q$ и $s$ содержат
$\frac{l}{2}$ и $\frac{l}{4}$ новых букв, соотвественно, а $r$ содержит
$\frac{l{-}1}{3}$ новых букв. Поскольку $l=k/2\ge5$, мы получаем $l\ge 16$.
Тогда $\frac{l{-}1}{3} > \frac{l}{4}$, откуда $w$ содержит более чем $k$ новых
букв, противоречие. Лемма доказана.
\end{proof}

\begin{proof}[Доказательство теоремы~\ref{art_weak}]
Пусть $w = uv$~--- слово над алфавитом из $k$ букв, $|u|=2k$, $v=\lfloor\frac{k}{2}\rfloor$.
От противного, предположим, что $w$ является абелево $\frac{k}{k{-}2}$-свободным словом.
Из леммы~\ref{lemma_art_weak2} мы получаем, что $u$ содержит $k$ различных букв, а из замечания~\ref{remark_art_weak}
мы получаем, что $v$ содержит $\lfloor\frac{k}{2}\rfloor$ различных букв. Это значит, что все буквы $v$ содержатся в $u$,
поэтому $w$ является слабой абелевой степенью с экспонентой $\frac{2k + \lfloor\frac{k}{2}\rfloor}{2k}$,
что не меньше $\frac{k}{k{-}2}$ при $k \ge 10$. Это невозможно, так как $w$ является абелево $\frac{k}{k{-}2}$-свободным.

Итак, любое слово над алфавитом из $k$ букв длины не меньше $2k + \lfloor\frac{k}{2}\rfloor$
содержит запрещённое подслово. Это означает,что язык абелевых $\frac{k}{k{-}2}$-слов конечен
и $ART_{w}(k) \ge \frac{k}{k{-}2}$.
\end{proof}
